Ranking Tournaments with No Errors

Abstract: We examine the classical problem of ranking a set of players on the basis of a set of pairwise comparisons arising from a sports tournament, with the objective of minimizing the total number of upsets, where an upset occurs if a higher ranked player was actually defeated by a lower ranked player. This problem can be rephrased as the so-called minimum feedback arc set problem on tournaments, which arises in a rich variety of applications and has been a subject of extensive research. We study this NP-hard problem using structure-driven and linear programming approaches.

Let $T=(V,A)$ be a tournament with a nonnegative integral weight $w(e)$ on each arc $e$. A subset $F$ of arcs is called a feedback arc set if $T\setminus F$ contains no cycles (directed). A collection $C$ of cycles (with repetition allowed) is called a cycle packing if each arc $e$ is used at most $w(e)$ times by members of $C$. We call $T$ cycle Mengerian if, for every nonnegative integral function ${w}$ defined on $A$, the minimum total weight of a feedback arc set is equal to the maximum size of a cycle packing. In this talk, we will discuss the characterization that a tournament is cycle Mengerian if and only if it contains none of four Möbius ladders as a subgraph. (Joint work with Guoli Ding, Wenan Zang, and Qiulan Zhao.)

combinatorics

Audience: researchers in the topic

Comments: pw 121323

---

SCMS Combinatorics Seminar

Series comments: Check scmscomb.github.io/ for more information

---